package leetcode.code117;

import leetcode.helper.tree.Node;

public class Solution1 extends Solution117 {

	@Override
	public Node connect(Node root) {
		if (root == null)
			return root;
		//链接当前节点的left，right
		if (root.left != null) {
			if (root.right != null) {
				root.left.next = root.right;
			} else {
				root.left.next = this.findNext(root.next);
			}
		}
		if (root.right != null && root.next != null) {
			root.right.next = this.findNext(root.next);
		}
		this.connect(root.right);//先连右侧，//链接right
		this.connect(root.left);// 链接 left
		return root;
	}

	private Node findNext(Node temp) {
		while (temp != null) {
			if (temp.left != null) {
				return temp.left;
			} else if (temp.right != null) {
				return temp.right;
			} else {
				temp = temp.next;
			}
		}
		return null;
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
//		so.debug1();
//		so.debug2();
//		so.debug3();
		so.debug4();
	}

}
